﻿using System;
using System.Collections.Generic;
using System.Drawing;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace AVL
{
    class AVLTree
    {
        public AVLNode[] stack = new AVLNode[50];

        public AVLNode root, A, B;

        public int top = 0, optop;

        public bool twice = false, opadd = true,ava = true;

        int []opstack = { 1, 2, 1, 2 };

        // 分裂后的 两颗树
        public AVLTree one, other;

        private void setroot(AVLNode no)
        {
            root = no;
            root.x = 360;
            root.y = 30;
            root.level = 1;
        }

        //  用 栈 输出
        public void paintAVLByStack(Graphics page)
        {
            if(root == null) return;
         //   InitPaintXY();
           setroot(root);
           //  setLeft(root);
            //
            top = 0;
            position(root);
            Pen penblack = new Pen(Color.Black);//创建红色笔对象
            SolidBrush black = new SolidBrush(Color.Black);//创建蓝色刷子对象
            AVLNode node;
            top = 0;
            stack[++top] = root;

            while (top > 0 && stack[top] != null)
            {
                node = stack[top--];
                if (node.left != null)
                {
                    stack[++top] = node.left;

                    page.DrawLine(penblack, node.x+ 20 , node.y + 40, node.left.x + 20 , node.left.y);
                }
                if (node.right != null)
                {
                    stack[++top] = node.right;
                    page.DrawLine(penblack, node.x + 20, node.y + 40, node.right.x + 20, node.right.y);
                }
                page.DrawEllipse(new Pen(node.color), node.x, node.y, 40, 40);
                Font font1 = new Font("Serif", 8);
                String st = node.data + "";
                int k = st.Length;
                page.DrawString(st, new Font("Serif", 15), black, node.x + 9, node.y + 6);
                page.DrawString("B:" + node.balance, font1, black, node.x + 6, node.y - 20);
                page.DrawString("L:" + node.level, font1, black, node.x + 40, node.y + 6);
                page.DrawString("H:" + node.hight, font1, black, node.x -20, node.y + 6);
            }

            //Font font = new Font("Serif", 15);
            //page.DrawString("height  data  bf", font, black, 6, 43);
            //   page.DrawEllipse(penblack, 50, 20, 36, 36);
        }

        //  层次遍历 初始化坐标
        public void InitPaintXY()
        {
            AVLNode node;
            //重置 root 坐标
            top = 0;
            setroot(root);
            stack[++top] = root;
            while (top > 0 && stack[top] != null)
            {   
                node = stack[top--];
                if (node.left != null)
                {
                    node.left.x = node.x - root.x / (node.left.level * 2 - 2);
                    node.left.y = node.y + 150;
                    stack[++top] = node.left;
                   
                }
                if (node.right != null)
                {
                    node.right.x = node.x + root.x / (node.right.level * 2 - 2);
                    node.right.y = node.y + 150;
                    stack[++top] = node.right;
                }
            }
        }

       public AVLNode find(int s)
        {
            AVLNode current = root;
            while (current != null)
            {
                current.color = Color.Blue;
                if (current.data == s)
                    return current;
                if (current.data > s)
                    current = current.left;
                else
                    current = current.right;
            }
            return null;
        }

        public void resetcolor(AVLNode no) {
		    if (no == null)
			    return;
		    no.color = Color.Green;
		    resetcolor(no.left);
		    resetcolor(no.right);
	    }

       public int insert(int s){
           int status = 0;

		    resetcolor(root);
		    A = null;
		   twice = false;

		    if (root == null) {
			    root = new AVLNode();
			    root.data = s;
			    root.x = 380;
			    root.y = 30;
			    root.level = 1;
			    root.hight = 1;              
            }
            else
                status = insert(s, root);
		    if (A != null)
			    A.color = Color.Yellow;
            return status;
		   // repaint();
	    }


        //   递归  插入
       private int insert(int s, AVLNode no)
       {
           int status = 0;
		    if (s == no.data) {
			    return -1;
		    }
		    if (s > no.data) {
			    if (no.right == null) {
				    AVLNode nn = new AVLNode();
				    no.right = nn;
				    nn.data = s;
				    nn.father = no;
				    nn.x = no.x + (250 - 70 * no.level);
				    nn.y = no.y + 150;
				    if (no.level == 4)
					    nn.x += 70;
				    nn.level = no.level + 1;
				    nn.hight = 1;
				    balance(nn);
			    } else
				  status = insert(s, no.right);
		    } else {
			    if (no.left == null) {
				    AVLNode nn = new AVLNode();
				    no.left = nn;
				    nn.data = s;
				    nn.father = no;
				    nn.x = no.x - (250 - 70 * no.level);
				    nn.y = no.y + 150;
				    if (no.level == 4)
					    nn.x -= 70;
				    nn.level = no.level + 1;
				    nn.hight = 1;
				    balance(nn);
			    } else
				  status = insert(s, no.left);
		    }
            return status;
	  }


        // 查入后 更新 树的 平衡因子
        private void balance(AVLNode no)
        {
            while (no != null)
            {
                int l = 0, r = 0;
                if (no.left != null)
                    l = no.left.hight;
                if (no.right != null)
                    r = no.right.hight;
                no.balance = l - r;
                no.hight = l > r ? (l + 1) : (r + 1);
                // 第一个不平衡点  赋值  给 A
                if (A == null && (no.balance == -2 || no.balance == 2))
                {
                    A = no;
                   // print();
                }
                no = no.father;
            }
        }

        //public void updateHight(AVLNode no)
        //{

        //    if (no == null) return;
        //    if (no.left == null && no.right == null)
        //    {
        //        no.balance = 0;
        //        return;
        //    }
        //    no.hight = AVLNodeHight(no);

        //    if (no.left != null)
        //    {
        //        updateHight(no.right);
        //    }
        //    if (no.right != null)
        //    {
        //        updateHight(no.right);
        //    }

        //}

        //public void updateTreeBF(AVLNode no){
          
        //    if (no == null) return;
        //    if (no.left != null && no.right != null)
        //    {
        //        no.balance = no.left.hight - no.right.hight;
        //        if (A == null && (no.balance == -2 || no.balance == 2)) {
        //        A = no;
        //        }
        //    }
        //    else if (no.left == null && no.right != null)
        //    {
        //        no.balance = 0 - no.right.hight;
        //        if (A == null && (no.balance == -2 || no.balance == 2)) {
        //        A = no;
        //        }
        //    }
        //    else if (no.left != null && no.right == null)
        //    {
        //        no.balance = no.left.hight;
        //        if (A == null && (no.balance == -2 || no.balance == 2)) {
        //        A = no;
        //        }
        //    }else
        //    {
        //        no.balance = 0;
        //    }
        //    if (no.left != null)
        //    {
        //        updateTreeBF(no.left);
        //    }
        //    if (no.right != null)
        //    {
        //        updateTreeBF(no.right);
        //    }
        //}

 ////         递归 求 节点 高度
 //       int AVLNodeHight(AVLNode T)
 //       {
 //           int left, right;
 //           if (null == T) return 0;
 //           else
 //           {

 //               left = AVLNodeHight(T.left);
 //               right = AVLNodeHight(T.right);
 //           }
 //           return 1 + (left > right ? left : right);
 //       }



        //   栈  插入
        public bool Add(int value) //添加一个元素
        {   //如果是空树，则新结点成为二叉排序树的根
            if (root == null)
            {
                root = new AVLNode();
                root.data = value;
                root.x = 380;
                root.y = 30;
                root.level = 1;
                root.hight = 1;
                return true;
            }
            top = 0;
            //prev为上一次访问的结点，current为当前访问结点
            AVLNode prev = null, current = root;
            while (current != null)
            {
                stack[top++] = current; //将路径上的结点插入数组
                //如果插入值已存在，则插入失败
                if (current.data == value)
                {
                    return false;
                }
                prev = current;
                //当插入值小于当前结点，则继续访问左子树，否则访问右子树
                current = (value < prev.data) ? prev.left : prev.right;
            }
            current = new AVLNode(); //创建新结点
            current.data = value;
            current.balance = 0;
            if (value < prev.data) //如果插入值小于双亲结点的值
            {
                prev.left = current; //成为左孩子
               
            }
            else //如果插入值大于双亲结点的值
            {
                prev.right = current; //成为右孩子
            }
            //  一些赋值
            current.father = prev;
            current.level = prev.level + 1;


            stack[top] = current; //将新元素插入数组path的最后
            //修改插入点至根结点路径上各结点的平衡因子
            int bf = 0;
            while (top > 0)
            {   //bf表示平衡因子的改变量，当新结点插入左子树，则平衡因子+1
                //当新结点插入右子树，则平衡因子-1
                bf = (value < stack[top - 1].data) ? 1 : -1;
                stack[--top].balance += bf; //改变当父结点的平衡因子
                bf = stack[top].balance; //获取当前结点的平衡因子
                //判断当前结点平衡因子，如果为0表示该子树已平衡，不需再回溯
                //而改变祖先结点平衡因子，此时添加成功，直接返回
                if (bf == 0)
                {
                    return true;
                }
                else if (bf == 2 || bf == -2) //需要旋转的情况
                {
                   // RotateSubTree(bf);
                    return true;
                }
            }
            return true;
        }
        public void delete(AVLNode no)
        {
            AVLNode p = no.father;
            A = null;
            optop = 0;
            twice = false;
            if (no.left != null && no.right != null)// 删除前驱
            {
                AVLNode s = no.left, ps = no;
                while (s != null)
                {
                    ps = s;
                    s = s.right;
                }
                no.data = ps.data;
                delete(ps);
                return;
            }
            if (no.left == null && no.right == null)
            {
                if (p == null)
                {
                    root = null;
                    return;
                }
                if (p.left != null && p.left.data == no.data)
                    p.left = null;
                else
                    p.right = null;
                if (p.left == null && p.right == null)
                    p.hight = 1;
                balance(p);
                if (A != null)
                    A.color = Color.Yellow;
                return;
            }
            if (no.left == null)
            {
                no.data = no.right.data;
                no.right = null;
                no.hight = 1;
                balance(no);
            }
            else
            {
                no.data = no.left.data;
                no.left = null;
                no.hight = 1;
                balance(no);
            }
            if (p == null)
                root = no;
            if (A != null)
                A.color = Color.Yellow;
        }

      //删除指定值
        public bool Remove(int value) 
        {
            top = -1;
            //parent表示双亲结点，node表示当前结点
            AVLNode node = root;
            //寻找指定值所在的结点
            while (node != null)
            {
                stack[++top] = node;
                //如果找到，则调用RemoveNode方法删除结点
                if (value == node.data)
                {
                    RemoveNode(node);//现在p指向被删除结点
                    return true; //返回true表示删除成功
                }
                if (value < node.data)
                {   //如果删除值小于当前结点，则向左子树继续寻找
                    node = node.left;
                }
                else
                {   //如果删除值大于当前结点，则向右子树继续寻找
                    node = node.right;
                }
            }
            return false; //返回false表示删除失败
        }
        //删除指定结点
        private void RemoveNode(AVLNode node)
        {
            AVLNode tmp = null;
            //当被删除结点存在左右子树时
            if (node.left != null && node.right != null)
            {
                tmp = node.left; //获取左子树
                stack[++top] = tmp;
                while (tmp.right != null) //获取node的中序遍历前驱结点，并存放于tmp中
                {   //找到左子树中的最右下结点
                    tmp = tmp.right;
                    stack[++top] = tmp;
                }
                //用中序遍历前驱结点的值代替被删除结点的值
                node.data = tmp.data;
                node.x = tmp.x;
                node.y = tmp.y;

                if (stack[top - 1] == node)
                {
                    stack[top - 1].left = tmp.left;
                }
                else
                {
                    stack[top - 1].right = tmp.left;
                }
            }
            else //当只有左子树或右子树或为叶子结点时
            {   //首先找到惟一的孩子结点
                tmp = node.left;
                if (tmp == null) //如果只有右孩子或没孩子
                {
                    tmp = node.right;
                }
                if (top > 0)
                {
                    if (stack[top - 1].left == node)
                    {   //如果被删结点是左孩子
                        stack[top - 1].left = tmp;
                    }
                    else
                    {   //如果被删结点是右孩子
                        stack[top - 1].right = tmp;
                    }
                }
                else  //当删除的是根结点时
                {
                    root = tmp;
                  //  updateLevel();
                }
            }
            if (top > 0) { 
                balance(stack[top - 1]);
            }
            ////删除完后，现在top指向实际被删除的结点
            //int data = node.data;
            //while (top > 0)
            //{   //bf表示平衡因子的改变量，当删除的是左子树中的结点时，平衡因子-1
            //    //当删除的是右子树的孩子时，平衡因子+1
            //    int bf = (data <= stack[top - 1].data) ? -1 : 1;
            //    stack[--top].balance += bf; //改变当父结点的平衡因子
            //    bf = stack[top].balance; //获取当前结点的平衡因子
            //    if (bf != 0) //如果bf==0，表明高度降低，继续后上回溯
            //    {
            //        //如果bf为1或-1则说明高度未变，停止回溯，如果为2或-2，则进行旋转
            //        //当旋转后高度不变，则停止回溯
            //       // if (bf == 1 || bf == -1 || !RotateSubTree(bf))
            //        if (bf == 1 || bf == -1)
            //        {
            //            break;
            //        }
            //    }
            //}

            position(root);
        }

        //private void updateLevel(AVLNode root){
             
        //    AVLNode node;
        //    top = 0;
        //    stack[++top] = root;
        //    while (top > 0 && stack[top] != null)
        //    {
        //        node = stack[top--];
        //        if (node.left != null)
        //        {
        //            node.left.level = node.level + 1;

        //        }
        //        if (node.right != null)
        //        {
        //            node.right.level = node.level + 1;
        //        }
        //    }
        
        //}

        private void rRotate(AVLNode t)
        {
            AVLNode p = t.left;
            int temp = t.data;
            t.data = p.data;
            p.data = temp;
            t.left = p.left;


            if (p.left != null)
                p.left.father = t;

            p.left = p.right;
            p.right = t.right;


            if (t.right != null)
                t.right.father = p;

            t.right = p;
        }


        // 更新整颗树高度 平衡因子
        public void rotateBalance() {
            top = 0;
            TreeToStack(root);
            while (top-- > 0)
                balance(stack[top]);
        }


        void lRotate(AVLNode t)
        {
            AVLNode p = t.right;
            int temp = p.data;
            p.data = t.data;
            t.data = temp;
            t.right = p.right;
            if (p.right != null)
                p.right.father = t;
            p.right = p.left;
            p.left = t.left;
            if (t.left != null)
                t.left.father = p;
            t.left = p;
            p.father = t;
        }


        private void position(AVLNode no)
        {
            //都是 重画root树
            if (no == null) return;
            if (no.left == null && no.right == null)
            {
                no.hight = 1;
                stack[top++] = no;
            }
            if (no.left != null)
            {
                no.left.x = no.x - (250 - 70 * no.level);
                no.left.y = no.y + 150;
                if (no.level == 4)
                    no.left.x -= 50;
                no.left.level = no.level + 1;
                position(no.left);
            }
            if (no.right != null)
            {
                no.right.x = no.x + (250 - 70 * no.level);
                no.right.y = no.y + 150;
                if (no.level == 4)
                    no.right.x += 50;
                no.right.level = no.level + 1;
                position(no.right);
            }
        }

        public string addRotate()
        {
            AVLNode no = A;
            string info = "";
            if (A == null) return info;
            //  LL 型
            if (no.balance == 2 && no.left.balance == 1)
            {
                rRotate(no);
                rotateBalance();
                info = "LL 型调整";
            }

            //  LR 型
            if (no.balance == 2 && no.left.balance == -1)
            {
                if (twice)
                {
                    rRotate(no);
                    twice = false;
                    rotateBalance();
                    info = "LR 型 第二次调整";
                }
                else
                {
                    lRotate(no.left);
                    twice = true;
                    info = "LR 型 第一次调整";
                }
              
            }

            //  RR 型
            if (no.balance == -2 && no.right.balance == -1)
            {
                lRotate(no);
                rotateBalance();
                info = "RR 型调整";
            }

            //  RL 型
            if (no.balance == -2 && no.right.balance == 1)
            {
                if (twice)
                {
                    lRotate(no);
                    twice = false;
                    rotateBalance();
                    info = " RL 型 第二次调整";
                }
                else
                {
                    rRotate(no.right);
                    twice = true;
                    info = " RL 型 第一次调整";
                }
                
            }
        //    updateHight(root);
            return info;
        }


        public void split(int data)
        {
           one = new AVLTree();
            
           other = new AVLTree();
           top = 0;
            TreeToStack(root);
            for (top = top - 1; top >= 0; top--)
            {
                if (stack[top].data <= data)
                {
                    one.adjustTree(stack[top].data);
                }
                else {
                    other.adjustTree(stack[top].data);
                }
            }
        }
    
        public void TreeToStack(AVLNode node){
            if (node == null) return;
            stack[top++] = node;
            if (node.left != null)
            {
                TreeToStack(node.left);
            }
            if (node.right != null)
            {
                TreeToStack(node.right);
            }
        }

        //将B 合并到 A;
        public void mergeAVLTree(AVLTree A, AVLTree B)
        {
            top = 0;
            TreeToStack(B.root);
            for (top = top - 1; top >= 0; top--)
            {
                A.adjustTree(stack[top].data);
            }
        }

        public void adjustTree(int data)
        {
            if (ava)
            {
                // 声明为 插入操作
                opadd = true;
                insert(data);
            }
            optop = 0;
            for (int j = 1; j <= 4; j++)
            {
                // 说明 为RR 或 LL   twice  没有改变    //  twice 为false 不用 两次
                if (j == 3 && !twice)
                    return;
                next();
                if (A == null)
                    return;
            }

        }

      

     //   public void adjustAVLTree(AVLTree tree)
     //   {
     //       if (tree == null) return ;
     ////       updateHight(tree.root);
     //       updateLevel(tree.root);
     ////       updateTreeBF(tree.root);
     //   }

        private string deleterotate()
        {
            string info = "";
            if (A == null) return info;
            AVLNode no = A;
            if (no.balance == 2 && no.left.balance > -1)
            { 
                rRotate(no);
                rotateBalance();
                info = "LL 型调整";
            }
            if (no.balance == 2 && no.left.balance == -1)
                if (twice)
                {
                    rRotate(no);
                    rotateBalance();
                    twice = false;
                    info = "LR 型 第二次调整";
                }
                else
                {
                    lRotate(no.left);
                    twice = true;
                    info = "LR 型 第一次调整";
                }
            if (no.balance == -2 && no.right.balance < 1)
            { 
                lRotate(no);
                rotateBalance();
                info = "RR 型调整";
            }
            if (no.balance == -2 && no.right.balance == 1)
            {
                if (twice)
                {
                    lRotate(no);
                    rotateBalance();
                    twice = false;
                    info = " RL 型 第二次调整";
                }
                else
                {
                    rRotate(no.right);
                    twice = true;
                    info = " RL 型 第一次调整";
                }
            }
            return info;
        }

        private void showB()
        {
            if (A == null)
                return;
            if (twice)
            {
                B.color = Color.Green;
                B = A;
            }
            else
            {
                // RR  或LL 型 时 B 就是  A
                B = A;
                // RL  型
                if (A.balance == 2 && A.left.balance == -1)
                    B = A.left;
                // LR  型
                if (A.balance == -2 && A.right.balance == 1)
                    B = A.right;
            }
            B.color = Color.Red;
        }

        public string next()
        {
            string s = "";
            if (opstack[optop] == 1)
                showB();
            if (opstack[optop] == 2)
            {
                if (opadd)
                    s = addRotate();
                else
                    s =deleterotate();
            }
            optop++;

            //  调整完成
            if (optop == 4 || (optop == 2 && !twice))
            {
                optop = 0;
                A = null;
                resetcolor(root);
            }
            return s;
        }
    }
}
